/**
 * @author LKQ
 * @date 2022/2/16 11:24
 * @description 动态规划，如果s[i] = 1，此时结束那么不影响，dp[i] = dp[i-1];
 * 如果s[i]=0,此时以0结束不符合，那么有两种可能：一、将此处0变为1 dp[i]= dp[i-1] + 1,
 * 二、将前面s[0, i-1]中所有1都变为0，两种取操作次数最少。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.minFlipsMonoIncr("10001");
    }
    public int minFlipsMonoIncr(String s) {
        int dp = 0, cnt = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '1') {
                ++cnt;
            } else {
                dp = Math.min(dp + 1, cnt);
            }
        }
        return dp;
    }
}
